package com.yulan.dp;

/**
 * 高楼扔鸡蛋
 */
public class drop_egg {
    /**
     *
     * @param m 楼层数
     * @param n 鸡蛋数
     */

    public int dropEgg1(int m,int n){
        if(m==0)
            return 0;
        if(m==1)
            return 1;
        if(n==1)
            return m;

        int[][] dp = new int[m+1][n+1];
        for(int i = 0;i<=m;i++){
            dp[i][0] = 0;
            dp[i][1] = 1;
        }
        for(int i = 0;i<n;i++){
            dp[1][i] = i;
            dp[0][i] = 0;
        }
        for(int i = 2;i<=n;i++){
            for(int j = 2;j<=n;j++){
                int res = j;
                for(int k = 1;k<=n;k++){
                    if(j>=k){
                        dp[i][j] = Math.max(dp[i-1][k-1],dp[i][j-k])+1;
                        if(res > dp[i][j])
                            res = dp[i][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}























